1168C - And Reachability - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
#define euyia ios::sync_with_stdio(0)
#define endl '\n'

#define ar array<int, 2>
#define arr array<int, 3>
int mod = 998244353; //1e9+7;
const int N = 3e5 + 5;
int t, n, m, k;
const int M = 19;
int a[N], b[M], f[N][M];
int main()
{
    euyia;
#ifdef DEBUG
    freopen("../1.in", "r", stdin);
#endif
    // 如果当前有。。那么当前就是最近的能获取y位的数字。。
    // 如果没有。。那么就通过自己有的中转点。。中转到最近的有x的地方。。
    // 这题jiangly写的好熟练。。
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    memset(b, -1, sizeof b);
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j < 19; j++)
            f[i][j] = n + 1;
    
    for (int i = n ; i > 0; --i) {
        for (int x = 0; x < 19; ++x) {
            if (a[i] >> x & 1) {
                f[i][x] = i;
            } else {
                for (int y = 0; y < 19; ++y)
                    if ((a[i] >> y & 1) && b[y] != -1)
                        f[i][x] = std::min(f[i][x], f[b[y]][x]);
            }
        }
        for (int x = 0; x < 19; ++x)
            if (a[i] >> x & 1)
                b[x] = i;
    }
    while (m--)
    {
        int x, y;
        cin >> x >> y;
        bool ok = 0;
        for (int i = 0; i < 19; ++i)
            if (f[x][i] <= y && a[y] >> i & 1)
                ok = 1;
        cout << (ok ? "Shi" : "Fou") << endl;
    }
};